package suanfa;

public class ZSolution
{

    /**
     * Z字形反转
     */
    public String convert(String s, int numRows) {

        if(numRows == 1) return s;
        int[] rowIdx = new int[numRows];
        char[] chars = new char[s.length()];
        int n = 0;
        int burketSize = numRows * 2 - 2;
        int burketNum = chars.length / burketSize;
        int rem = chars.length % burketSize;
        for(int i = 1; i < numRows; i ++){
            int flag = i == 1 ? 1 : 2;
            n = flag * burketNum + (rem >= i ? ( 1 + (burketSize - rem + 1 < i ? 1 : 0)) : 0);
            rowIdx[i] = rowIdx[i-1] + n;
        }
        int flag = -1;
        int curRow = 0;
        for(char c : s.toCharArray()){
            chars[rowIdx[curRow]] = c;
            rowIdx[curRow] = rowIdx[curRow] + 1;
            if (curRow == 0 || curRow == numRows - 1) flag = -flag;
            curRow += flag;
        }
        return new String(chars);
    }

    public static void main(String[] args)
    {
        ZSolution solution = new ZSolution();
        String leetcode = solution.convert("LEETCODEISHIRING", 3);
        System.out.println(leetcode);

        String s = solution.covert1("LEETCODEISHIRING", 3);
        System.out.println(s);
    }


    /**
     * 算法的时间复杂度是O(n)
     */
    public String covert1(String s, int numRows)
    {

        if (s == null || s.length() == 0 || numRows <= 1)
        {
            return s;
        }
        StringBuilder stringBuilder = new StringBuilder(s.length());

        int a,j;

        for (int i = 0; i < numRows; ++i)
        {
            a = 0;
            j = i;
            while (true)
            {
                if (j < s.length())
                {
                    stringBuilder.append(s.charAt(j));
                }else break;

                //这里是关键的一步
                if ((a ^= 1) == 1)
                {
                    j += 2 * ((numRows - i - 1) == 0 ? i : numRows - i - 1);
                }else
                {
                    j += 2 * (i == 0 ? numRows - i - 1 : i);
                }
            }
        }

        return stringBuilder.toString();
    }
}
